package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;
import xyz.scootaloo.util.CollectionComparator;

/**
 * @author flutterdash@qq.com
 * @since 2021/3/24 21:57
 */
public class P338 {

    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        int highByte = 0;
        for (int i = 1; i<=num; i++) {
            if ((i & (i - 1)) == 1)
                highByte = i;
            res[i] = res[i - highByte] + 1;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] expect = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2};
        Tester.createTest(new P338()::countBits)
                .addCase(12, expect)
                .setMatcher(CollectionComparator::compareIntArray)
                .test();
    }

}
